// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-01 10:44
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com;

import com.DataStruct.Tree.TwoBinaryTree.TreeDiameter;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 计算给定图中每一个节点的最远距离
 */
class Solution {
    final int maxn = (int) 1e4 + 10;
    int[] head = new int[maxn];
    int maxdis, maxv, idx = 0;
    // 记录树的指定到达树中所有节点的距离
    int[] d1 = new int[maxn], d2 = new int[maxn];
    Edge[] edges = new Edge[2 * maxn];

    {
        Arrays.fill(head, -1);
    }

    void add(int u, int v, int w) {
        edges[idx] = new Edge(v, head[u], w);
        head[u] = idx++;
    }


    class Edge {
        int to, next, w;

        public Edge(int to, int next, int w) {
            this.to = to;
            this.next = next;
            this.w = w;
        }
    }

    void dfs(int u, int fa, int d2s, int[] d) {
        d[u] = d2s;
        if (d[maxv] < d[u]) {
            maxdis = d2s;
            maxv = u;
        }
        for (int e = head[u]; e != -1; e = edges[e].next) {
            int v = edges[e].to, w = edges[e].w;
            if (v == fa) {
                continue;
            }
            dfs(v, u, d2s + w, d);
        }
    }


    /**
     * 方法测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] es = {{0, 1, 1}, {0, 2, 4}, {1, 3, 1}, {1, 4, 1}, {3, 5, 1}};
        Solution td = new Solution();
        // 初始化边信息
        for (int[] e : es) {
            td.add(e[0], e[1], e[2]);
            td.add(e[1], e[0], e[2]);
        }

        int[] dist = new int[6];

        // 第一次dfs
        td.dfs(0, -1, 0, td.d1);
        // 第二次dfs
        td.maxdis = 0;
        int start = td.maxv;
        td.dfs(start, -1, 0, td.d1);
        int end = td.maxv;
        td.dfs(end, -1, 0, td.d2);
        System.out.println("树的直径 = " + td.maxdis);
        for (int i = 0; i < 6; i++) {
            dist[i] = Math.max(td.d1[i], td.d2[i]);
            System.out.println(dist[i]);
        }
    }

}
